package leetcode.new_wrold;

public class T37 {
    boolean[][] row = new boolean[10][10];
    boolean[][] col = new boolean[10][10];
    boolean[][] box = new boolean[10][10];

    public void solveSudoku(char[][] board) {
        init(board);
        DFS(board,0,0);
    }

    private boolean DFS(char[][] board,int i,int j){
        if (i==8 && j==9){
            return true;
        }
        if (j==9){
            j=0;
            i++;
        }
        System.out.println("i="+i+",j="+j+",board[i][j]="+board[i][j]);
        if (board[i][j]!='.'){
            return DFS(board, i, j + 1);
        }

        //穷举1-9
       for (int k=1;k<=9;k++){
           int z = i/3*3 +j/3;
           if (!(row[i][k] || col[j][k]||box[z][k])){
               System.out.println("i="+i+",j="+j+",board[i][j]="+board[i][j]+"尝试k="+(char)(k+'0'));
               board[i][j] = (char) (k+'0');
               row[i][k] = true;
               col[j][k] = true;
               box[z][k] = true;

               if (DFS(board,i,j+1)){
                   return true;
               }
               row[i][k] = false;
               col[j][k] = false;
               box[z][k] = false;
               board[i][j] = '.';
           }
       }
        return false;
    }

    private void init(char[][] board){
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char ch  = board[i][j];
                if (ch=='.') continue;
                int k = ch-'0';
                int z = i/3 * 3 + j/3;
                row[i][k] = true;
                col[j][k] = true;
                box[z][k] = true;
            }
        }
    }

    public static void main(String[] args) {
        T37 t37 = new T37();
        char[][] board = new char[][]{
                {'5','3','.','.','7','.','.','.','.'},
                {'6','.','.','1','9','5','.','.','.'},
                {'.','9','8','.','.','.','.','6','.'},
                {'8','.','.','.','6','.','.','.','3'},
                {'4','.','.','8','.','3','.','.','1'},
                {'7','.','.','.','2','.','.','.','6'},
                {'.','6','.','.','.','.','2','8','.'},
                {'.','.','.','4','1','9','.','.','5'},
                {'.','.','.','.','8','.','.','7','9'}
        };
        t37.solveSudoku(board);

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j]+" ");
            }
            System.out.println();
        }
    }

}
